//递归的时间复杂度  O(logN)
//分区操作的时间复杂度  O(n)
//时间复杂度 O(n*logN)  最好的情况是每次选择完都排到中间，最坏的情况是有序或者逆序
Array.prototype.quickSort = function() {
  const rec = (arr) => {
    if (arr.length <= 1) { return arr }
    const left = []
    const right = []
    const mid = arr[0]
    for (let i = 1; i < arr.length; i++) {
      if (arr[i] < mid) {
        left.push(arr[i])
      } else {
        right.push(arr[i])
      }
    }
    return [...rec(left), mid, ...rec(right)]
  }
  const res = rec(this)
  res.forEach((n, i) => this[i] = n)
}

const arr = [2, 4, 5, 3, 1]
arr.quickSort()
console.log(arr)
